import java.util.ArrayList;
import java.util.List;

/**
 * 全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 */
public class Test46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        dfs(ret,list,nums,0,nums.length-1);
        return ret;
    }
    public void dfs(List<List<Integer>> ret,List<Integer> list,int[] nums,int begin,int end){
        if (begin == end){
            list.add(nums[begin]);
            ret.add(list);
            return;
        }
        for (int i = begin; i <= end; i++) {
            list.add(nums[i]);
            if (begin > 0) swap(nums,i,begin);
            dfs(ret,list,nums,begin+1,end);
        }
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
